#include <napi/native_api.h>
#include <vector>
#include <queue>
#include <limits>
#include <utility>
#include <algorithm>
#include <string>

// 保留原有的Add函数
static napi_value Add(napi_env env, napi_callback_info info)
{
    size_t argc = 2;
    napi_value args[2] = {nullptr};

    napi_get_cb_info(env, info, &argc, args , nullptr, nullptr);

    napi_valuetype valuetype0;
    napi_typeof(env, args[0], &valuetype0);

    napi_valuetype valuetype1;
    napi_typeof(env, args[1], &valuetype1);

    double value0;
    napi_get_value_double(env, args[0], &value0);

    double value1;
    napi_get_value_double(env, args[1], &value1);

    napi_value sum;
    napi_create_double(env, value0 + value1, &sum);

    return sum;
}

// Dijkstra算法实现
static napi_value DijkstraAlgorithm(napi_env env, napi_callback_info info)
{
    // 获取参数
    size_t argc = 3;
    napi_value args[3] = {nullptr};
    napi_get_cb_info(env, info, &argc, args, nullptr, nullptr);
    
    // 检查参数数量
    if (argc != 3) {
        napi_throw_error(env, nullptr, "需要三个参数: 邻接矩阵、顶点数和起始顶点");
        return nullptr;
    }
    
    // 检查参数类型
    bool isArray;
    napi_is_array(env, args[0], &isArray);
    if (!isArray) {
        napi_throw_type_error(env, nullptr, "第一个参数必须是邻接矩阵数组");
        return nullptr;
    }
    
    // 获取顶点数
    uint32_t vertexCount;
    napi_get_value_uint32(env, args[1], &vertexCount);
    
    // 获取起始顶点
    uint32_t startVertex;
    napi_get_value_uint32(env, args[2], &startVertex);
    
    if (startVertex >= vertexCount) {
        napi_throw_range_error(env, nullptr, "起始顶点必须小于顶点总数");
        return nullptr;
    }
    
    // 获取邻接矩阵
    std::vector<std::vector<int>> graph(vertexCount, std::vector<int>(vertexCount, 0));
    uint32_t arrayLength;
    napi_get_array_length(env, args[0], &arrayLength);
    
    if (arrayLength != vertexCount) {
        napi_throw_error(env, nullptr, "邻接矩阵行数必须等于顶点数");
        return nullptr;
    }
    
    // 解析邻接矩阵
    for (uint32_t i = 0; i < vertexCount; i++) {
        napi_value row;
        napi_get_element(env, args[0], i, &row);
        
        bool isRowArray;
        napi_is_array(env, row, &isRowArray);
        if (!isRowArray) {
            napi_throw_type_error(env, nullptr, "邻接矩阵的每一行必须是数组");
            return nullptr;
        }
        
        uint32_t rowLength;
        napi_get_array_length(env, row, &rowLength);
        
        if (rowLength != vertexCount) {
            napi_throw_error(env, nullptr, "邻接矩阵的每一行长度必须等于顶点数");
            return nullptr;
        }
        
        for (uint32_t j = 0; j < vertexCount; j++) {
            napi_value element;
            napi_get_element(env, row, j, &element);
            
            int value;
            napi_get_value_int32(env, element, &value);
            graph[i][j] = value;
        }
    }
    
    // 执行Dijkstra算法
    const int INF = std::numeric_limits<int>::max();
    std::vector<int> dist(vertexCount, INF);
    std::vector<bool> visited(vertexCount, false);
    std::vector<int> prev(vertexCount, -1);
    
    dist[startVertex] = 0;
    
    // 使用优先队列优化
    std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> pq;
    pq.push({0, startVertex});
    
    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();
        
        if (visited[u]) continue;
        visited[u] = true;
        
        for (int v = 0; v < vertexCount; v++) {
            // 如果有边且未访问过
            if (graph[u][v] > 0) {
                int weight = graph[u][v];
                if (dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                    prev[v] = u;
                    pq.push({dist[v], v});
                }
            }
        }
    }
    
    // 创建结果对象
    napi_value result, distances, paths;
    napi_create_object(env, &result);
    napi_create_array(env, &distances);
    napi_create_array(env, &paths);
    
    // 填充距离数组
    for (uint32_t i = 0; i < vertexCount; i++) {
        napi_value distValue;
        if (dist[i] == INF) {
            napi_create_int32(env, -1, &distValue); // -1表示不可达
        } else {
            napi_create_int32(env, dist[i], &distValue);
        }
        napi_set_element(env, distances, i, distValue);
    }
    
    // 填充路径数组
    for (uint32_t i = 0; i < vertexCount; i++) {
        napi_value path;
        napi_create_array(env, &path);
        
        if (i != startVertex && dist[i] != INF) {
            std::vector<int> pathVec;
            int current = i;
            while (current != -1) {
                pathVec.push_back(current);
                current = prev[current];
            }
            std::reverse(pathVec.begin(), pathVec.end());
            
            for (uint32_t j = 0; j < pathVec.size(); j++) {
                napi_value vertex;
                napi_create_int32(env, pathVec[j], &vertex);
                napi_set_element(env, path, j, vertex);
            }
        } else if (i == startVertex) {
            // 起点到自己的路径就是自己
            napi_value vertex;
            napi_create_int32(env, startVertex, &vertex);
            napi_set_element(env, path, 0, vertex);
        }
        
        napi_set_element(env, paths, i, path);
    }
    
    // 设置结果对象的属性
    napi_set_named_property(env, result, "distances", distances);
    napi_set_named_property(env, result, "paths", paths);
    
    return result;
}

EXTERN_C_START
static napi_value Init(napi_env env, napi_value exports)
{
    napi_property_descriptor desc[] = {
        { "add", nullptr, Add, nullptr, nullptr, nullptr, napi_default, nullptr },
        { "dijkstra", nullptr, DijkstraAlgorithm, nullptr, nullptr, nullptr, napi_default, nullptr }
    };
    napi_define_properties(env, exports, sizeof(desc) / sizeof(desc[0]), desc);
    return exports;
}
EXTERN_C_END

static napi_module demoModule = {
    .nm_version = 1,
    .nm_flags = 0,
    .nm_filename = nullptr,
    .nm_register_func = Init,
    .nm_modname = "dijkstra",
    .nm_priv = ((void*)0),
    .reserved = { 0 },
};

extern "C" __attribute__((constructor)) void RegisterDijkstraModule(void)
{
    napi_module_register(&demoModule);
}
